package Leetcode.Dichotomy;

import java.util.List;

/**
 * @Author: kirito
 * @Date: 2024/4/10 12:30
 * @Description:
 * 假设你是一家合金制造公司的老板，你的公司使用多种金属来制造合金。现在共有 n 种不同类型的金属可以使用，并且你可以使用 k 台机器来制造合金。每台机器都需要特定数量的每种金属来创建合金。
 *
 * 对于第 i 台机器而言，创建合金需要 composition[i][j] 份 j 类型金属。最初，你拥有 stock[i] 份 i 类型金属，而每购入一份 i 类型金属需要花费 cost[i] 的金钱。
 *
 * 给你整数 n、k、budget，下标从 1 开始的二维数组 composition，两个下标从 1 开始的数组 stock 和 cost，请你在预算不超过 budget 金钱的前提下，最大化 公司制造合金的数量。
 *
 * 所有合金都需要由同一台机器制造。
 *
 * 返回公司可以制造的最大合金数。
 *
 *
 *
 * 示例 1：
 *
 * 输入：n = 3, k = 2, budget = 15, composition = [[1,1,1],[1,1,10]], stock = [0,0,0], cost = [1,2,3]
 * 输出：2
 * 解释：最优的方法是使用第 1 台机器来制造合金。
 * 要想制造 2 份合金，我们需要购买：
 * - 2 份第 1 类金属。
 * - 2 份第 2 类金属。
 * - 2 份第 3 类金属。
 * 总共需要 2 * 1 + 2 * 2 + 2 * 3 = 12 的金钱，小于等于预算 15 。
 * 注意，我们最开始时候没有任何一类金属，所以必须买齐所有需要的金属。
 * 可以证明在示例条件下最多可以制造 2 份合金。
 * 示例 2：
 *
 * 输入：n = 3, k = 2, budget = 15, composition = [[1,1,1],[1,1,10]], stock = [0,0,100], cost = [1,2,3]
 * 输出：5
 * 解释：最优的方法是使用第 2 台机器来制造合金。
 * 要想制造 5 份合金，我们需要购买：
 * - 5 份第 1 类金属。
 * - 5 份第 2 类金属。
 * - 0 份第 3 类金属。
 * 总共需要 5 * 1 + 5 * 2 + 0 * 3 = 15 的金钱，小于等于预算 15 。
 * 可以证明在示例条件下最多可以制造 5 份合金。
 * 示例 3：
 *
 * 输入：n = 2, k = 3, budget = 10, composition = [[2,1],[1,2],[1,1]], stock = [1,1], cost = [5,5]
 * 输出：2
 * 解释：最优的方法是使用第 3 台机器来制造合金。
 * 要想制造 2 份合金，我们需要购买：
 * - 1 份第 1 类金属。
 * - 1 份第 2 类金属。
 * 总共需要 1 * 5 + 1 * 5 = 10 的金钱，小于等于预算 10 。
 * 可以证明在示例条件下最多可以制造 2 份合金。
 *
 *
 * 提示：
 *
 * 1 <= n, k <= 100
 * 0 <= budget <= 108
 * composition.length == k
 * composition[i].length == n
 * 1 <= composition[i][j] <= 100
 * stock.length == cost.length == n
 * 0 <= stock[i] <= 108
 * 1 <= cost[i] <= 100
 */

public class maxNumberOfAlloys {
    /**
     * 感觉就是这个计算思路不是很清晰，首先还是得根据题意来模拟思路写一下
     * @param n     n台机器
     * @param k     k类金属
     * @param budget    预算
     * @param composition   i j  代表i台机器合成j类金属需要的原材料
     * @param stock     代表第i类金属有多少库存
     * @param cost      购入一份 i 类型金属需要花费 cost[i] 的金钱
     * @return
     */
    public int maxNumberOfAlloys(int n, int k, int budget, List<List<Integer>> composition, List<Integer> stock, List<Integer> cost) {
        int left = 1, right = 200000000, ans = 0;
        while (left <= right) {
            int mid = (left + right) / 2;
            boolean valid = false;
            for (int i = 0; i < k; ++i) {
                long spend = 0;
                for (int j = 0; j < n; ++j) {
                    spend += Math.max((long) composition.get(i).get(j) * mid - stock.get(j), 0) * cost.get(j);
                }
                if (spend <= budget) {
                    valid = true;
                    break;
                }
            }
            if (valid) {
                ans = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return ans;
    }

    public int maxNumberOfAlloys2(int n, int k, int budget, List<List<Integer>> composition, List<Integer> stock, List<Integer> cost) {
        // 全部转成 int[] 数组，效率比 List<Integer> 更高
        int[] stocks = toArray(stock);
        int[] costs = toArray(cost);

        int ans = 0;
        for(List<Integer> c : composition)
            ans = calculate(budget, toArray(c), stocks, costs, ans);

        return ans;
    }
    //集合转换为数组
    private int[] toArray(List<Integer> list) {

        int[] arr = new int[list.size()];
        for(int i = 0; i < arr.length;i++)
            arr[i] = list.get(i);

        return arr;
    }
    //检查
    private boolean check(int budget, int[] compositions, int[] stocks, int[] costs, int count) {

        for(int i = 0; i < compositions.length; ++i) {
            int delta =  compositions[i] * count - stocks[i];
            if(delta <= 0) continue;

            budget -= delta * costs[i];
            if(budget < 0)
                return false;
        }

        return true;
    }
    //二分
    private int calculate(int budget, int[] compositions, int[] stocks,int[] costs, int count) {
        if(!check(budget, compositions, stocks, costs, count + 1))
            return count;

        count = count + 1;
        while(check(budget, compositions, stocks, costs, count << 1))
            count <<= 1;

        int left = count,  right = count << 1;
        while(left <= right) {
            int mid = left + right >> 1;
            if(check(budget, compositions, stocks, costs, mid))
                left = mid + 1;
            else
                right = mid - 1;
        }

        return right;
    }
}
